package cn.datastruct.Algorithm;

import java.util.Arrays;

/**
 * 2021/3/19 22:00
 * 背包问题思路：
 * 1.int[] w,表示物品的重量
 * 2.int[] val,表示对应物品的价值
 * 3.int[i][j] v,表示总共有i个物品，重量为j能够存储的最大价值
 * 4.v[i][0] = v[0][j] = 0 初始化为零
 * 5.w[i] > j,表示第i个物品的重量大于容量，不能填入，v[i][j] = v[i-1][j],用前面的物品能够填入的价值最大来替代
 * 6.j>=w[i],表示第i个物品的重量小于容量，能够填入，v[i][j] = max{v[i - 1][j], val[i] + v[i-1][j-w[i]]}
 */
public class KnapsackProblem {
    public static void main(String[] args) {
        int[] w = {1, 4, 3, 2, 1};//表示商品的重量
        int[] val = {1500, 3000, 2000, 1700, 1000};//表示商品的价值
        int m = 7;//表示背包的容量
        int n = val.length;//表示物品的数目
        int[][] v = new int[n + 1][m + 1];//多出一行一列初始化为零，v[i][j]表示当前情况最大的价值
        int[][] path = new int[n + 1][m + 1];//记录路径
        for (int i = 0; i < m; i++) {
            v[0][i] = 0;
        }
        for (int i = 0; i < n; i++) {
            v[i][0] = 0;
        }
        for (int i = 1; i < n + 1; i++) {//跳过第一行
            for (int j = 1; j < m + 1; j++) {//跳过第一列
                if (w[i - 1] > j) {
                    v[i][j] = v[i - 1][j];
                } else {
                    if(v[i - 1][j] < val[i - 1] + v[i - 1][j - w[i - 1]]) {
                        v[i][j] = val[i - 1] + v[i - 1][j - w[i - 1]];
                        path[i][j] = 1;//填入一个物品
                    }else {
                        v[i][j] = v[i - 1][j];
                    }
                }
            }
        }
        for (int[] ints : v) {
            System.out.println(Arrays.toString(ints));
        }
        int i = n;
        int j = m;
        while(i > 0 && j > 0){
            if(path[i][j] == 1) {
                System.out.println("第" + i + "个商品已填入");
                j -= w[i - 1];
            }
            i--;
        }
    }
}
